package com.gofaraway.service.student.leetCodeV2;

/**
 * @author ChenPeng
 * @Date 2024/11/21 15:31
 */
public class 验证回文串 {

    /**
     * 变种问题：
     * 如何判断一个字符串是否是回文字符串的问题，我想你应该听过，我们今天的题目就是基于这个问题的改造版本。如果字符串是通过单链表来存储的，那该如何来判断是一个回文串呢？
     */
    public boolean isPalindrome(ListNode head) {
        // 利用快慢指针找到链表中点，即 快指针每步前进两步 慢指针每步前进一步
        // 在慢指针前进的过程中，同时修改其next，反转前半段链表，最后比较前后子串

        if (head == null || head.next == null) {
            return true;
        }

        ListNode pre = null;
        ListNode slow = head;
        ListNode fast = head;

        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;

            ListNode next = slow.next;
            slow.next = pre;
            pre = slow;
            slow = next;
        }

        if (fast != null) {
            slow = slow.next;
        }

        while (slow != null) {
            if (slow.val != pre.val) {
                return false;
            }
            slow = slow.next;
            pre = pre.next;
        }

        return true;
    }



    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {val = x;}
    }
}
